//
// Created by 紫霄 on 2020/4/25.
//

#ifndef LEETCODE_57_H
#define LEETCODE_57_H
#include <vector>
using namespace std;
//// 迭代二分查找；垃圾！！
/*

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    int sz = nums.size();
    int min = nums[0];
    int max = nums[sz - 1];
    vector<int> ans;
    if (min - 1 < target && target < 2 * max + 1) {
      for (int i = 0; i < sz; ++i) {
        int need = target - nums[i];
        int lo = i + 1;
        int hi = sz - 1;
        if (need <= max) {
          while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] > need) {
              hi = mid - 1;
            }
            if (nums[mid] < need) {
              lo = mid + 1;
            }
            if (nums[mid] == need) {
              ans.push_back(need);
              ans.push_back(nums[i]);
              return ans;
            }
          }
        }
      }
    }
    return ans;
  }
};

*/

// 双指针 牛逼！！
class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    int lo = 0;
    int hi = nums.size() - 1;
    vector<int> ans;
    while (lo != hi) {
      if (nums[lo] + nums[hi] < target) {
        ++lo;
      } else if (nums[lo] + nums[hi] > target) {
        --hi;
      } else {
        ans.push_back(nums[lo]);
        ans.push_back(nums[hi]);
        return ans;
      }
    }
    return ans;
  }
};
#endif // LEETCODE_57_H
